1. Field of the Invention
The present invention relates to routing of information packets in a communications network, and, more particularly, to a router determining shortest paths for communicating packets between nodes based on shortest-path trees.
2. Description of the Related Art
In an interconnected communications network employing packets, such as the Internet, routing protocols are employed by routers of the network to determine how packets are to be forwarded between nodes. Packets received by a node""s router are forwarded to other nodes based on a forwarding table of an interior routing protocol. Interior routing protocols exchange network topology and link-state information (xe2x80x9cnetwork topology informationxe2x80x9d) among routers to allow the node""s router to construct the corresponding forwarding table. An example of a widely-used interior routing protocol is the Open Shortest Path First (OSPF) protocol, as outlined in J. Moy, xe2x80x9cOSPF Version 2,xe2x80x9d Internet Draft, Request for Comment (RFC) 2178, July, 1997. In addition, some interior routing protocols associate a link cost, known in the art as a weight, with each link between nodes. The link cost may be associated with, for example, available bandwidth or revenue generated by the link. When link-state information (e.g., status, utilization, connectivity, or bandwidth) is exchanged between routers, each router in a regional network has a complete description of the network""s topology.
Each router computes paths between nodes, and uses the weights to calculate a set of preferred paths. Each of the set of preferred paths that is computed has a minimum total weight for the path between the particular router and each other router in the region. This set of preferred paths may be defined with a shortest path tree (SPT). A forwarding table with routing information (e.g., source-destination pair, source ports, and destination ports) is generated from the SPT. The router uses the routing information to forward a received packet along the shortest path of the SPT to its destination. The SPT may be calculated using an algorithm such as Dijkstra""s algorithm, described in E. Dijkstra, xe2x80x9cA note: two problems in connection with graphs,xe2x80x9d Numerical Mathematics, vol. 1, 1959, pp. 269-271.
When the network topology of a regional network changes (e.g., a link fails, recovers, or changes its routing weights), each router in the region detects the change and updates the network topology information stored by the router. After updating its stored network topology information, each router recalculates a new SPT and forwarding table. In routers of the prior art, the recalculation deletes the current SPT and recalculates the new SPT from scratch (this type of recalculation method is known in the art as a statis algorithm).
However, for most changes in network topology, the new SPT does not differ significantly from the old SPT, and in many cases the old and new SPTs are the same. Statis algorithms that recompute the new SPT from scratch are inefficient because they do not take advantage of available information about the prior (outdated) SPT. Another drawback of statis algorithms is that multiple routes of the same shortest distance may coexist from one router to another router. When the SPT is re-computed from scratch, a different one of the coexisting multiple routes may be selected for the SPT than was selected by a prior computation. If a new path of the coexisting multiple routes is selected each time the new SPT is computed, the router may change many entries in its forwarding table frequently and unnecessarily, increasing the risk of routing errors or routing failures associated with implementing the change in routing.
To illustrate, FIG. 1 shows a regional network 100 of an Internet Service Provider (ISP) comprising four routers 101, 102, 103, and 104. The routers 101, 102, and 104 are commonly known as access routers and provide users a connection to the network 100. Router 103 connects the network 100 to a backbone packet network 105 that may be, for example, the Internet. Initially, link 106 (shown by a dashed arrow) between 103 and 104 is not in service (i.e., disconnected or not provisioned). The solid arrows indicate links which are preferred paths defined by an SPT calculated and stored in router 101 (commonly termed as an SPT xe2x80x9crooted atxe2x80x9d router 101). The numeral next to each solid arrow in FIG. 1 is the weight assigned to the corresponding link. The forwarding table in router 101 contains forwarding entries, each forwarding entry corresponding to next-hop information of each user""s network connection through router 103 to the backbone packet network 105. Initially, all packets routed from router 101 to backbone packet network 105 pass through router 102. However, if the link between routers 103 and 104 is established (i.e., either provisioned or recovered) and has a link weight of 1, the network topology changes and the SPT rooted at router 101 must be recomputed.
When the SPT is recomputed from scratch, the result may indicate that all paths to the backbone packet network 105 from router 101 now pass through router 104. Router 101 then changes the next-hop information for some or all network connections passing through router 103 to now pass through router 104. However, the path weight for the previous and new paths are the same and the changes may not be necessary. These changes may correspond to several thousand updates in the forwarding table of router 101, many of which may be redundant updates. In addition to redundant updates in forwarding tables, unnecessary changes in the SPT may also cause undesirable fluctuation of traffic load on any given route.
The present invention relates to routing packets in a packet network based on a shortest path tree (SPT) defining paths between nodes in the network. In accordance with the present invention, a temporary list of nodes in the network is generated for a current SPT, the list including nodes affected by a change in the weight of a link between two nodes in the network. The change in weight corresponds to the addition of a new link in the network or an increase or decrease in the weight of an existing link in the network. A selection process selects a node of the list in accordance with a maximum decrement criterion, the maximum decrement criterion identifying the node in the list having a most negative or a least positive associated distance change resulting from the change in the weight of the link. An update process updates one or more paths in current SPT for nodes reachable from the selected node, wherein the selected node is removed from the list and zero, one, or more of the reachable nodes are added to the list. The selection process and update process are repeated until the list is empty to generate an updated SPT. A router, for example, then routes one or more packets in accordance with the updated SPT.